#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <string>
using namespace std;
class Solution 
{
public:
	int minDistance(string word1, string word2) 
	{
		// Start typing your C/C++ solution below
		// DO NOT write int main() function
		size_t s1 = word1.size(), s2 = word2.size();
		int** dist = new int*[s1+1];
		for(size_t i=0;i<=s1;i++)
		{
			dist[i] = new int[s2+1];
			memset(dist[i],0,sizeof(int) * (s2+1));
		}

		for(size_t i=1;i<=s2;i++)
			dist[0][i] = i;

		for(size_t i=1;i<=s1;i++)
			dist[i][0] = i;

		for(size_t i=1;i<=s1;i++)
			for(size_t j=1;j<=s2;j++)
			{
				int curMin = min(dist[i][j-1]+1,dist[i-1][j]+1);
				int a = dist[i-1][j-1];
				if(word1[i-1] != word2[j-1])
					a++;
				dist[i][j] = min(curMin,a);
			}

		
		int result = dist[s1][s2];

		for(size_t i=0;i<=s1;i++)
			delete [] dist[i];

		delete [] dist;

		return result;

	}
};
#endif